package com.github.miniyk2012.coding2017.basic.queue;

import java.util.LinkedList;
import java.util.List;

/**
 * 用Queue来实现Josephus问题
 * 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数：
 * N个人围成一圈（位置记为0到N-1）， 并且从第一个人报数， 报到M的人会被杀死， 直到最后一个人留下来
 * 该方法返回一个List， 包含了被杀死人的次序
 * @author liuxin
 *
 */
public class Josephus {
	
	public static List<Integer> execute(int n, int m){		
		CircleQueue<Integer> circleQueue = new CircleQueue<>(n);
		List<Integer> result = new LinkedList<>();
		for (int i=0; i<n; i++) {
            circleQueue.enQueue(i);
        }
        int num = 1;  // 从1开始报数
        while (!circleQueue.isEmpty()) {
			Integer x = circleQueue.deQueue();
			if (num == m) {
			    num = 1;  // 如果数到m，则杀死该人，下一个人从1开始报数
			    result.add(x);
            } else {
			    num++;
			    circleQueue.enQueue(x);
            }
		}
        return result;
	}

	
}
